package com.heima.leetcode.practice;

/**
 * leetcode 35. 搜索插入位置
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/6 22:49
 */
public class E35 {

    /**
     * <h3>解决思路就是用改动版的二分查找，推荐使用</h3>
     * @param nums 目标数组
     * @param target 目标值
     * @return 返回目标值在数组中的位置，如果没有，返回插入的位置
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0; // 左边界，包含
        int right = nums.length; // 右边界，不包含，多用这种不包含的
        while (left < right){
            int median = (left + right) >>> 1; // 避免溢出
            if (nums[median] < target){
                left = median + 1;
            } else if (nums[median] > target){
                right = median;
            } else {
                return median;
            }
        }
        return left; // 肯定有一种状态：left+1 = right，此时待查找元素位于这俩之间，插入位置明显就是left+1，进入最后一轮刚好left也会自增一
    }
}
